package primary.code07_Greedy;

/**
 * 棋盘 N 皇后问题
 *
 * @author Yudi Wang
 * @date 2021/8/9 15:09
 */
public class Code07_Queen {

    /**
     * n 皇后问题
     *
     * @param n
     * @return
     */
    private static int queen(int n) {
        if (n < 3) {
            return 0;
        }
        int limit = (1 << n) -1;
        return queenTest(n, 0, limit, 0, 0, 0);
    }

    /**
     * @param n           皇后数量
     * @param row         当前摆放皇后的行号
     * @param limit       可摆放列号的限制
     * @param columnLimit 列限制 (所在位为1, 表示该列不能放皇后)
     * @param leftLimit   左斜线限制
     * @param rightLimit  右斜线限制
     * @return
     */
    private static int queen(int n, int row, int limit,
                             int columnLimit, int leftLimit, int rightLimit) {
        //base case, 一种成功摆放方式
        if (row >= n) {
            return 1;
        }
        //计算当前可以排放皇后的列号（1 表示可以放置皇后）
        int totalLimit = columnLimit | leftLimit | rightLimit;
        int allowColumn = ~totalLimit & limit;
        int res = 0;
        //循环可以摆放的位置
        while (allowColumn != 0) {
            int column = (~allowColumn + 1) & allowColumn;//获取最低为1
            res += queen(n, row + 1, limit,
                    columnLimit | column,
                    (leftLimit | column) << 1,
                    (rightLimit | column) >>> 1);
            allowColumn = ~column & allowColumn;//最低位1置为0
        }
        return res;
    }

    /**
     * 思路：采用递归的思想，将大问题拆分到最终个直接解决的小问题
     *
     * 过滤掉4种限制后，确定当前行皇后可用的位置（1表示）
     * 初始化摆放方式种类结果
     * while 可用的位置 != 0
     *      取可用位置的最后一位，作为本行皇后摆放位置
     *      可用的位置最后一位更新为0
     *      更新3项限制
     *      递归调用，将问题分解为 row+1 行处理，返回摆放方式种类
     *      增加摆放方式种类结果
     * end
     *
     * 100100
     * 011011
     * 011100
     * @param n 皇后数量
     * @param row 当前处理第row行皇后
     * @param limit 限制
     * @param columnLimit 列限制
     * @param leftLimit 左对角线限制
     * @param rightLimit 右对角线限制
     * @return 剩余的皇后有多少种摆法
     */
    private static int queenTest(int n, int row, int limit, int columnLimit, int leftLimit, int rightLimit) {
        if (row >= n) {
            return 1;
        }
        int res = 0;
        int availablePositions = limit & (~(columnLimit | leftLimit | rightLimit));
        while (availablePositions != 0) {
            int position = availablePositions & (~availablePositions + 1);
            availablePositions = availablePositions & ~position;
            res += queenTest(n, row + 1, limit,
                    columnLimit | position, (leftLimit | position) << 1, (rightLimit | position) >>> 1);
        }
        return res;
    }

    /**
     * 12皇后问题可排放数量：14200
     * 13皇后问题可排放数量：73712
     * 14皇后问题可排放数量：365596
     * @param args
     */
    public static void main(String[] args) {
        int n = 14;
        final int res = queen(n);
        System.out.println(n + "皇后问题可排放数量：" + res);
    }
}
